package util;

public class BinarySearchUtil {

    public static void main(String[] args) {

        int[] nums = {1, 2, 3, 5, 6, 6, 6,9};
        System.out.println(lowerBound(nums, 6));
    }
    /**
     * 返回第一个小于等于key的值，-1表示未找到
     */
    public static int lowerBound(int[] nums, int target) {
        if (nums == null) {
            return -1;
        }
        int start = 0;
        int end = nums.length;
        int middle;
        while (start < end) {
            middle = start + (end - start) / 2;
            if (middle == start) {
                break;
            }
            if (nums[middle] == target) {
                end = middle;
            } else if (nums[middle] < target) {
                start = middle;
            } else {
                end = middle - 1;
            }
        }
        System.out.println("start: " + start + " end:" + end);
        if (nums[start] > target) {
            return -1;
        }
        return nums[end] <= target ? end : start;
    }

    /**
     * 返回第一个大于等于key的值，length表示未找到
     */
    public static int upperBound(int[] nums, int target) {
        if (nums == null) {
            return -1;
        }
        int start = 0;
        int end = nums.length;
        int middle;
        while (start < end) {
            middle = start + (end - start) / 2;
            if (nums[middle] == target) {
                end = middle;
            } else if (nums[middle] < target) {
                start = middle + 1;
            } else {
                end = middle;
            }
        }
        if (nums[end] < target) {
            return nums.length;
        }
        return nums[start] >= target ? start : end;
    }
}
